package datastructure;

import java.util.EnumSet;

/**
 * @author ZCR
 * @create 2025/8/28 21:27
 * 304. 二维区域和检索 - 矩阵不可变
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 *
 * 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
 * 实现 NumMatrix 类：
 *
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
 */
public class NumMatrix {
    int[][] prefixSum;

    public NumMatrix(int[][] matrix) {
        prefixSum = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                prefixSum[i][j] = (i >= 1 ? prefixSum[i - 1][j] : 0) + (j >= 1 ? prefixSum[i][j - 1] : 0) - (i >= 1 && j >= 1 ? prefixSum[i - 1][j - 1] : 0) + matrix[i][j];
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2][col2] - (row1 >= 1 ? prefixSum[row1 - 1][col2] : 0) - (col1 >= 1 ? prefixSum[row2][col1 - 1] : 0) + (row1 >= 1 && col1 >= 1 ? prefixSum[row1 - 1][col1 - 1] : 0);
    }

    public static void main(String[] args) {
        int [][]matrix = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
        NumMatrix numMatrix = new NumMatrix(matrix);
        System.out.println(numMatrix.sumRegion(2,1,4,3));
        System.out.println(numMatrix.sumRegion(1,1,2,2));
        System.out.println(numMatrix.sumRegion(1,2,2,4));
    }
}
